package alogrithm;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/11/4 19:03
 */
public class KMPTest1 {
    public static void main(String[] args) {
        final int i = KMP("ababababf", "ababf");
        System.out.println(i);
    }


    public static int KMP(String text, String pattern) {
        int m = text.length();
        int n = pattern.length();
        int[] next = new int[n];
        getNext(next, pattern);
        for (int i = 0, j = 0; i < m; ++i) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == n) {
                return (i - n + 1);
            }
        }
        return -1;
    }

    private static void getNext(int[] next, String pattern) {
        int n = pattern.length();
        next[0] = 0;
        int j = 0;
        for (int i = 1; i < n; ++i) {
            if (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }

}
